<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>使数组严格递增</title>
</head>
<body>
  <script>
    function fn(arr1, arr2) {
      // 因为只需要考虑操作数, 不需要考虑索引具体位置, 并且保证 arr1 严格递增, 那么 arr2 每个元素只会使用一次, 对 arr2 去重后进行排序
      arr2 = Array.from(new Set(arr2)).sort((a, b) => a - b)
      // 向前向后添加一个数字 (重点), 来保证可以得到严格递增
      arr1 = [-1, ...arr1, Infinity]
      const N = arr1.length
      // dp 定义为从 [0, i) 的严格递增的最小操作数, 注意并不包括 i
      const dp = Array(N).fill(Infinity)
      // 初始化
      dp[0] = 0
      for (let i = 1; i < N; i++) {
        if (arr1[i - 1] < arr1[i]) dp[i] = dp[i - 1]
        // 关键在于每一个值都需要判断是否需要替换
        const idx = search(arr1[i])
        // Math.min(idx, i - 1) 应该理解为限制替换的次数, 因为替换是要从 [0,i) 与 [0, idx] 进行
        // j 的意义就是 [0, i) 中替换了 j 次
        for (let j = 1; j <= Math.min(i - 1, idx); j++) {
          // 已经确定了 arr1 的替换位置, 也确定了 arr2 找到满足题意元素的位置
          // 那么从两个确定位置向左同时查找 j 步, 然后再比较arr1与arr2元素是否存在相同关系
          // 因为 arr1 要保证严格递增, 并且 arr2 通过预处理已经去重加排序, 也是严格递增
          // 如果满足条件那么就直接进行批量替换, 然后在比较 dp 的值
          if (arr1[i - 1 - j] < arr2[idx - j])
            dp[i] = Math.min(dp[i], dp[i - j - 1] + j)
        }
      }
      function search(target) {
        let left = 0
        let right = arr2.length
        while (left < right) {
          let mid = (left + right) >> 1
          if (arr2[mid] >= target) {
            right = mid
          } else {
            left = mid + 1
          }
        }
        return left
      }
      // 如果最后一个稳定为 Infinity, 那么说明无法操作
      return dp[N - 1] >= Infinity ? -1 : dp[N - 1]
    }
    console.log(fn([1, 5, 3, 6, 7], [1, 3, 2, 4]))
  </script>
</body>
</html>